home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / lib / include / tclHash.h < prev    next >
C/C++ Source or Header  |  1992-12-17  |  5KB  |  148 lines
  1. /*
  2.  * tclHash.h --
  3.  *
  4.  *    This header file declares the facilities provided by the
  5.  *    Tcl hash table procedures.
  6.  *
  7.  * Copyright 1991 Regents of the University of California
  8.  * Permission to use, copy, modify, and distribute this
  9.  * software and its documentation for any purpose and without
  10.  * fee is hereby granted, provided that the above copyright
  11.  * notice appear in all copies.  The University of California
  12.  * makes no representations about the suitability of this
  13.  * software for any purpose.  It is provided "as is" without
  14.  * express or implied warranty.
  15.  *
  16.  * $Header: /sprite/src/lib/tcl/RCS/tclHash.h,v 1.3 91/08/27 11:36:04 ouster Exp $ SPRITE (Berkeley)
  17.  */
  18.  
  19. #ifndef _TCLHASH
  20. #define _TCLHASH
  21.  
  22. #ifndef _TCL
  23. #include <tcl.h>
  24. #endif
  25.  
  26. /*
  27.  * Structure definition for an entry in a hash table.  No-one outside
  28.  * Tcl should access any of these fields directly;  use the macros
  29.  * defined below.
  30.  */
  31.  
  32. typedef struct Tcl_HashEntry {
  33.     struct Tcl_HashEntry *nextPtr;    /* Pointer to next entry in this
  34.                      * hash bucket, or NULL for end of
  35.                      * chain. */
  36.     struct Tcl_HashTable *tablePtr;    /* Pointer to table containing entry. */
  37.     struct Tcl_HashEntry **bucketPtr;    /* Pointer to bucket that points to
  38.                      * first entry in this entry's chain:
  39.                      * used for deleting the entry. */
  40.     ClientData clientData;        /* Application stores something here
  41.                      * with Tcl_SetHashValue. */
  42.     union {                /* Key has one of these forms: */
  43.     char *oneWordValue;        /* One-word value for key. */
  44.     int words[1];            /* Multiple integer words for key.
  45.                      * The actual size will be as large
  46.                      * as necessary for this table's
  47.                      * keys. */
  48.     char string[4];            /* String for key.  The actual size
  49.                      * will be as large as needed to hold
  50.                      * the key. */
  51.     } key;                /* MUST BE LAST FIELD IN RECORD!! */
  52. } Tcl_HashEntry;
  53.  
  54. /*
  55.  * Structure definition for a hash table.  Must be in tcl.h so clients
  56.  * can allocate space for these structures, but clients should never
  57.  * access any fields in this structure.
  58.  */
  59.  
  60. #define TCL_SMALL_HASH_TABLE 4
  61. typedef struct Tcl_HashTable {
  62.     Tcl_HashEntry **buckets;        /* Pointer to bucket array.  Each
  63.                      * element points to first entry in
  64.                      * bucket's hash chain, or NULL. */
  65.     Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
  66.                     /* Bucket array used for small tables
  67.                      * (to avoid mallocs and frees). */
  68.     int numBuckets;            /* Total number of buckets allocated
  69.                      * at **bucketPtr. */
  70.     int numEntries;            /* Total number of entries present
  71.                      * in table. */
  72.     int rebuildSize;            /* Enlarge table when numEntries gets
  73.                      * to be this large. */
  74.     int downShift;            /* Shift count used in hashing
  75.                      * function.  Designed to use high-
  76.                      * order bits of randomized keys. */
  77.     int mask;                /* Mask value used in hashing
  78.                      * function. */
  79.     int keyType;            /* Type of keys used in this table. 
  80.                      * It's either TCL_STRING_KEYS,
  81.                      * TCL_ONE_WORD_KEYS, or an integer
  82.                      * giving the number of ints in a
  83.                      */
  84.     Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
  85.         char *key));
  86.     Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
  87.         char *key, int *newPtr));
  88. } Tcl_HashTable;
  89.  
  90. /*
  91.  * Structure definition for information used to keep track of searches
  92.  * through hash tables:
  93.  */
  94.  
  95. typedef struct Tcl_HashSearch {
  96.     Tcl_HashTable *tablePtr;        /* Table being searched. */
  97.     int nextIndex;            /* Index of next bucket to be
  98.                      * enumerated after present one. */
  99.     Tcl_HashEntry *nextEntryPtr;    /* Next entry to be enumerated in the
  100.                      * the current bucket. */
  101. } Tcl_HashSearch;
  102.  
  103. /*
  104.  * Acceptable key types for hash tables:
  105.  */
  106.  
  107. #define TCL_STRING_KEYS        0
  108. #define TCL_ONE_WORD_KEYS    1
  109.  
  110. /*
  111.  * Macros for clients to use to access fields of hash entries:
  112.  */
  113.  
  114. #define Tcl_GetHashValue(h) ((h)->clientData)
  115. #define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
  116. #define Tcl_GetHashKey(tablePtr, h) \
  117.     ((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
  118.                         : (h)->key.string))
  119.  
  120. /*
  121.  * Macros to use for clients to use to invoke find and create procedures
  122.  * for hash tables:
  123.  */
  124.  
  125. #define Tcl_FindHashEntry(tablePtr, key) \
  126.     (*((tablePtr)->findProc))(tablePtr, key)
  127. #define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
  128.     (*((tablePtr)->createProc))(tablePtr, key, newPtr)
  129.  
  130. /*
  131.  * Exported procedures:
  132.  */
  133.  
  134. extern void        Tcl_DeleteHashEntry _ANSI_ARGS_((
  135.                 Tcl_HashEntry *entryPtr));
  136. extern void        Tcl_DeleteHashTable _ANSI_ARGS_((
  137.                 Tcl_HashTable *tablePtr));
  138. extern Tcl_HashEntry *    Tcl_FirstHashEntry _ANSI_ARGS_((
  139.                 Tcl_HashTable *tablePtr,
  140.                 Tcl_HashSearch *searchPtr));
  141. extern char *        Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
  142. extern void        Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
  143.                 int keyType));
  144. extern Tcl_HashEntry *    Tcl_NextHashEntry _ANSI_ARGS_((
  145.                 Tcl_HashSearch *searchPtr));
  146.  
  147. #endif /* _TCLHASH */
  148.